{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.2-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个非空的整数数组，返回其中出现频率前 k 高的元素。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: nums = [1,1,1,2,2,3], k = 2\n",
    "输出: [1,2]\n",
    "示例 2:\n",
    "\n",
    "输入: nums = [1], k = 1\n",
    "输出: [1]\n",
    "说明：\n",
    "\n",
    "你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。\n",
    "你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。\n",
    "通过次数46,213提交次数76,006\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/top-k-frequent-elements\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最简单算法，扫描一遍数组放在map中($O(n)$), 取前k个，排序($O(nlogn)$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解法2，使用优先队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            dic.setdefault(i, 0)\n",
    "            dic[i] += 1\n",
    "        ans = []\n",
    "        ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[1, 1]"
     },
     "metadata": {},
     "execution_count": 30
    }
   ],
   "source": [
    "nums = [1,2,1,2]\n",
    "k = 2\n",
    "Solution().topKFrequent(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[1, 2]"
     },
     "metadata": {},
     "execution_count": 20
    }
   ],
   "source": [
    "import collections\n",
    "c = collections.Counter(nums)\n",
    "[i[0] for i in c.most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}